Grokking Oracle Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Oracle Easy
Count Number of Pairs With Absolute Difference K (easy)
Solution: Count Number of Pairs With Absolute Difference K
Degree of an Array (easy)
Solution: Degree of an Array
Find Subsequence of Length K With the Largest Sum (easy)
Solution: Find Subsequence of Length K With the Largest Sum
Rectangle Overlap (easy)
Solution: Rectangle Overlap
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Island Perimeter (easy)
Solution: Island Perimeter
Climbing Stairs (easy)
Solution: Climbing Stairs
Move Zeroes (easy)
Solution: Move Zeroes
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Valid Parentheses (Easy)
Solution: Valid Parentheses
Oracle Medium
Longest Palindromic Substring (medium)
Solution: Longest Palindromic Substring
Single Element in a Sorted Array (medium)
Solution: Single Element in a Sorted Array
Pairs of Songs With Total Durations Divisible by 60 (medium)
Solution: Pairs of Songs With Total Durations Divisible by 60
Search a 2D Matrix II (medium)
Solution: Search a 2D Matrix II
Minimize Maximum of Array (medium)
Solution: Minimize Maximum of Array
Asteroid Collision (medium)
Solution: Asteroid Collision
Combination Sum (medium)
Solution: Combination Sum
Binary Tree Right Side View (medium)
Solution: Binary Tree Right Side View
Sort Colors (medium)
Solution: Sort Colors
Group Anagrams (Medium)
Solution: Group Anagrams
Decode String (Medium)
Solution: Decode String
Number of Islands (medium)
Solution: Number of Islands
Binary Tree Zigzag Level Order Traversal (medium)
Solution: Binary Tree Zigzag Level Order Traversal
Longest Common Subsequence (medium)
Solution: Longest Common Subsequence
Rotting Oranges (medium)
Solution: Rotting Oranges
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Spiral Matrix (medium)
Solution: Spiral Matrix
Container With Most Water (Medium)
Solution: Container With Most Water
3Sum (medium)
Solution: 3Sum
Simplify Path (medium)
Solution: Simplify Path
Next Permutation (medium)
Solution: Next Permutation
Basic Calculator II (medium)
Solution: Basic Calculator II
Merge Intervals (medium)
Solution: Merge Intervals
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Longest Increasing Subsequence (medium)
Solution: Longest Increasing Subsequence
Validate Binary Search Tree (medium)
Solution: Validate Binary Search Tree
Integer to English Words (hard)
Solution: Integer to English Words
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Merge K Sorted Lists (hard)
Solution: Merge K Sorted Lists
Max Points on a Line (hard)
Solution: Max Points on a Line
Sudoku Solver (hard)
Solution: Sudoku Solver
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Constrained Subsequence Sum (hard)
Solution: Constrained Subsequence Sum
Solution: Rotting Oranges

Problem Statement

You are given an m x n matrix in which each cell can have one of three values:

  • 0 representing an empty cell,
  • 1 representing a fresh orange, or
  • 2 representing a rotten orange.

At each minute, any fresh orange becomes rotten if it is 4-directionally adjacent to a rotten orange.

Return the minimum number of minutes that should be passed until all the orange gets rotten. If it is impossible, return -1.

Examples

  • Input: grid =
[[2,1,0,0],
 [1,1,1,0],
 [0,1,1,1],
 [0,0,1,2]]
  • Expected Output: 3
  • Justification: The rotten oranges at (0,0) and (3,3) spread the rot to all adjacent fresh oranges. By day 4, all reachable fresh oranges are spoiled. The progression is as follows:
    • Minute 1: Oranges at positions (0, 1), (1, 0), (2, 3), and (3, 2) gets spoiled.
    • Minute 2: Oranges at positions (1, 1), and (2, 2) gets spoiled.
    • Minute 3: Oranges at positions (2, 1), and (1, 2) gets spoiled.

Example 2:

  • Input: grid =
[[2,1,1],
 [1,1,0],
 [0,1,2]]
  • Expected Output: 2
  • Justification: The rotten oranges spread the rot to all fresh oranges in 2 minutes, successfully spoiling all of them.

Example 3:

  • Input: grid =
[[0,2],
 [1,0],
 [0,1]]
  • Expected Output: -1
  • Justification: In any case, it is not possible that all oranges gets rotten.

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • grid[i][j] is 0, 1, or 2.

Solution

To solve this problem, we'll use a breadth-first search (BFS) approach, treating the grid as a graph where each cell is a node connected to its adjacent (up, down, left, right) cells. This method is effective because it allows us to spread the rot from all rotten oranges simultaneously, day by day, mimicking the natural process of spoilage spreading. By tracking the days as levels in our BFS traversal, we can determine the minimum time required to spoil all reachable fresh oranges or identify if any remain unreachable and thus, unsolvable.

Our approach starts by identifying all the initial rotten oranges and adding them to a queue as the starting point of our BFS. We also count the number of fresh oranges to keep track of the progress. On each day (or level of BFS), we take the current rotten oranges from the queue, spoil their adjacent fresh oranges, and then add those newly rotten oranges to the queue for the next day's process. This continues until either there are no fresh oranges left or we cannot reach any more fresh oranges, indicating an unsolvable situation.

Step-by-Step Algorithm

  1. Initialize a queue to keep track of the positions (row and column) of all initially rotten oranges. Also, maintain a counter to keep track of the number of fresh oranges present in the grid.

  2. Iterate over the grid to find and add all initially rotten oranges' positions to the queue and count the number of fresh oranges. This step helps to understand the starting point of the problem and the goal to achieve (i.e., to rot all fresh oranges, if possible).

  3. Perform a breadth-first search (BFS) from all initially rotten oranges simultaneously:

    • Increment a minute counter at the start of each level of BFS (each level represents a minute).
    • For each rotten orange in the queue, check its four adjacent cells (up, down, left, right). If an adjacent cell contains a fresh orange (denoted by 1), change it to a rotten orange (denoted by 2), decrement the fresh orange counter, and add its position to the queue for processing in the next minute.
    • Continue this process until the queue is empty or there are no more fresh oranges left to rot.
  4. After the BFS completion, check if there are any fresh oranges left:

    • If no fresh oranges are left (fresh orange counter is 0), return the total minutes elapsed as the result.
    • If there are still fresh oranges left, return -1 to indicate that not all oranges can be rotted.

Algorithm Walkthrough

Initial Setup

  • Grid:
    [[2,1,0,0],
     [1,1,1,0],
     [0,1,1,1],
     [0,0,1,2]]
    
  • Rotten Oranges Queue: [(0,0), (3,3)] (positions of initially rotten oranges).
  • Fresh Oranges Count: 8.

Minute 0: Start with two rotten oranges in the queue.

  • Queue: [(0,0), (3,3)]
  • Fresh Oranges: 8

Minute 1: Process the first level of the queue.

  • Dequeue (0,0). It rots the oranges at positions (1,0) and (0,1).
  • Dequeue (3,3). It rots the oranges at positions (2,3) and (3,2).
  • New rotten oranges added to the queue: [(1,0), (0,1), (2,3), (3,2)].
  • Grid After Minute 1:
    [[2,2,0,0],
     [2,1,1,0],
     [0,1,1,2],
     [0,0,2,2]]
    
  • Fresh Oranges: 4

Minute 2: Process the second level of the queue.

  • Dequeue and process (1,0), (0,1), (2,3), and (3,2). From these, only (1,0) and (2,3) have adjacent fresh oranges they can rot, specifically:
    • (0,1) directly rots (1,1).
    • (1,0) has no more fresh oranges to rot adjacent to it.
    • (2,3) rots (2,2).
    • (3,2) has no more fresh oranges to rot adjacent to it.
  • New rotten oranges added to the queue: [(1,1), (2,2)].
  • Grid After Minute 2:
    [[2,2,0,0],
     [2,2,1,0],
     [0,1,2,2],
     [0,0,2,2]]
    
  • Fresh Oranges: 2

Minute 3: Process the third level of the queue.

  • Dequeue and process (1,1) and (2,2). These new rotten oranges can rot the remaining fresh oranges at (2,1) and (1,2).
  • New rotten oranges added to the queue: [(2,1), (1,2)].
  • Grid After Minute 3:
    [[2,2,0,0],
     [2,2,2,0],
     [0,2,2,2],
     [0,0,2,2]]
    
  • Fresh Oranges: 0

Conclusion: By the end of Minute 3, all reachable fresh oranges have been spoiled, and the grid no longer contains any fresh oranges.

Code

Java

. . . .

Complexity Analysis

  • Time Complexity: The time complexity is , where (M) and (N) are the dimensions of the grid. This is because, in the worst case, each cell is visited at least once.
  • Space Complexity: The space complexity is in the worst case due to the queue potentially holding all the oranges if they are all rotten initially.
Rotting Oranges (medium)
Meeting Rooms II (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Initial Setup

Code

Complexity Analysis